# !/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time : 2023/4/25 20:40
# @Author : xyjiang1216
# @Email : jiangxuyan@nudt.edu.cn
# @File : itp_tabu.py
# @Version: OpenPlanner2.0
import math
from random import randint
from typing import List

from OpenPlanner.examples.itp_demo.itp_algo_input import ITPStream
from OpenPlanner.examples.itp_demo.itp_global_variables import TABU_TBL_SIZE, MAX_IN_NUM, STEP_SIZE, FAIL, SUCCESS, CANDIDATE_NUM, \
    RAND_MAX, TABU_ENTRY_UNEQUAL, TABU_ENTRY_EQUAL, MAX_LOOP_NUM, MAX_REPEAT_NUM
from OpenPlanner.examples.itp_demo.itp_sort import itp_multi_stage_sort


class schedInfo:
    def __init__(self, flow_id=0, offset=0, density=0, flag=FAIL):
        self.flow_id = flow_id
        self.offset = offset
        self.density = density
        self.flag = flag

    def sched_info_deepcopy(self,
                            flow_id,
                            offset,
                            density,
                            flag):
        self.flow_id = flow_id
        self.offset = offset
        self.density = density
        self.flag = flag


class tabuEntry:
    def __init__(self):
        self.out = [0 for i in range(STEP_SIZE)]
        # self.out = []
        self.inn = [0 for i in range(MAX_IN_NUM)]
        # self.inn = []
        self.in_num = 0

    def tabu_entry_deepcopy(self,
                            out,
                            inn,
                            in_num):
        self.out = [i for i in out]
        self.inn = [i for i in inn]
        self.in_num = in_num


class cqfResource:
    def __init__(self, total_len=0, used_len=0, free_len=0):
        self.total_len = total_len
        self.used_len = used_len
        self.free_len = free_len

    def cqf_resource_deepcopy(self,
                              total_len,
                              used_len,
                              free_len):
        self.total_len = total_len
        self.used_len = used_len
        self.free_len = free_len


# 全局队列资源
class globalResource:
    def __init__(self):
        self.cur_total_sched_slot_num = 0
        self.cqf_resource: List[List[cqfResource]] = []

    def global_resource_deepcopy(self,
                                 cur_total_sched_slot_num,
                                 cqf_resource):
        self.cur_total_sched_slot_num = cur_total_sched_slot_num
        for l_res in cqf_resource:
            link = [cqfResource(**q_res.__dict__) for q_res in l_res]
            self.cqf_resource.append(link)


class tabuSchedSolution:
    def __init__(self):
        self.cur_suc_num = 0
        self.cur_fail_num = 0
        self.entry = tabuEntry()
        # 该列表的长度是总的流量数目
        self.sched_suc: List[schedInfo] = []
        self.sched_fail: List[schedInfo] = []
        # 该列表的长度是总的链路数目
        # 只记录剩余的
        # self.g_resource = [0 for i in range(total_link)]
        self.g_resource: globalResource = globalResource()

    def init_sched_solution(self, total_stream):
        self.sched_suc = [schedInfo() for i in range(total_stream)]
        self.sched_fail = [schedInfo() for i in range(total_stream)]

    def solution_deepcopy(self,
                          cur_suc_num: int,
                          cur_fail_num: int,
                          entry: tabuEntry,
                          sched_suc: List[schedInfo],
                          sched_fail: List[schedInfo],
                          g_resource: globalResource
                          ):
        self.cur_suc_num = cur_suc_num
        self.cur_fail_num = cur_fail_num
        # 初始化entry
        self.entry = tabuEntry()
        self.entry.tabu_entry_deepcopy(**entry.__dict__)
        # 初始化sched_suc
        self.sched_suc = []
        for sched in sched_suc:
            si = schedInfo()
            si.sched_info_deepcopy(**sched.__dict__)
            self.sched_suc.append(si)
        # 初始化sched_fail
        self.sched_fail = []
        for sched in sched_fail:
            si = schedInfo()
            si.sched_info_deepcopy(**sched.__dict__)
            self.sched_fail.append(si)
        # 初始化g_resource
        self.g_resource = globalResource()
        self.g_resource.global_resource_deepcopy(**g_resource.__dict__)


class tabuTable:
    def __init__(self):
        self.cur_num = 0
        self.entry = [tabuEntry() for i in range(TABU_TBL_SIZE)]


# 仅供生成初始解时使用
class schedSet:
    def __init__(self):
        self.cur_flow_num = 0
        self.cur_suc_num = 0
        self.sched: List[schedInfo] = []


def _itp_generate_init_solution_random(stream_array: List[ITPStream],
                                       tsn_sched_set: schedSet,
                                       g_resource: globalResource,
                                       init_solution: tabuSchedSolution):
    for j in range(tsn_sched_set.cur_flow_num):
        if tsn_sched_set.sched[j].flag == SUCCESS:
            continue

        flow_id = tsn_sched_set.sched[j].flow_id
        period_in_slot = stream_array[flow_id].period_in_slot
        pkt_num = stream_array[flow_id].pkt_num

        offset = 0

        if randint(0, 1) == 1:
            offset = randint(0, period_in_slot - 1)
        else:
            continue

        flag = 0
        route_path = stream_array[flow_id].route
        total_slot_num_in_hyper_period = g_resource.cur_total_sched_slot_num
        hop = 0
        for link_id in route_path:
            for t in range(int(total_slot_num_in_hyper_period / period_in_slot)):
                slot = (offset + t * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                g_resource.cqf_resource[link_id][slot].used_len += pkt_num
                g_resource.cqf_resource[link_id][slot].free_len -= pkt_num
                if g_resource.cqf_resource[link_id][slot].free_len < 0:
                    flag = 1
            hop += 1

        if flag == 1:
            hop = 0
            for link_id in route_path:
                for t in range(int(total_slot_num_in_hyper_period / period_in_slot)):
                    slot = (offset + t * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                    g_resource.cqf_resource[link_id][slot].used_len -= pkt_num
                    g_resource.cqf_resource[link_id][slot].free_len += pkt_num
                hop += 1
            pass
        else:
            tsn_sched_set.sched[j].flag = SUCCESS
            tsn_sched_set.sched[j].offset = offset
            tsn_sched_set.cur_suc_num += 1

    init_solution.init_sched_solution(len(stream_array))
    for i in range(tsn_sched_set.cur_flow_num):
        if tsn_sched_set.sched[i].flag == SUCCESS:
            init_solution.sched_suc[init_solution.cur_suc_num] = schedInfo()
            init_solution.sched_suc[init_solution.cur_suc_num].sched_info_deepcopy(
                **tsn_sched_set.sched[i].__dict__
            )
            init_solution.cur_suc_num += 1
        else:
            init_solution.sched_fail[init_solution.cur_fail_num] = schedInfo()
            init_solution.sched_fail[init_solution.cur_fail_num].sched_info_deepcopy(
                **tsn_sched_set.sched[i].__dict__
            )
            init_solution.cur_fail_num += 1

    init_solution.g_resource = globalResource()
    init_solution.g_resource.global_resource_deepcopy(**g_resource.__dict__)


def _insert_flow_with_adjust_offset_random(sched: schedInfo,
                                           g_resource,
                                           stream_array: List[ITPStream]):
    flow_id = sched.flow_id
    period_in_slot = stream_array[flow_id].period_in_slot

    route = stream_array[flow_id].route
    route_len = len(route)

    pkt_num = stream_array[flow_id].pkt_num

    latency_req_in_slot = stream_array[flow_id].latency_req_in_slot

    offset = randint(0, period_in_slot - 1)

    latency = offset + route_len + 1

    total_slot_num_in_hyper_period = g_resource.cur_total_sched_slot_num

    if latency <= latency_req_in_slot:
        sched.flag = SUCCESS
        hop = 0
        for link_id in route:
            for j in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
                slot = (offset + j * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                if g_resource.cqf_resource[link_id][slot].free_len < pkt_num:
                    sched.flag = FAIL
                    break
            hop += 1
            if sched.flag == FAIL:
                break

        if sched.flag == SUCCESS:
            sched.offset = offset
            hop = 0
            for link_id in route:
                for j in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
                    slot = (offset + j * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                    g_resource.cqf_resource[link_id][slot].free_len -= pkt_num
                    g_resource.cqf_resource[link_id][slot].used_len += pkt_num
                hop += 1


def _compute_flow_density_path_variance(sched,
                                        offset,
                                        g_resource,
                                        stream_array: List[ITPStream]):
    flow_id = sched.flow_id
    route = stream_array[flow_id].route
    period_in_slot = stream_array[flow_id].period_in_slot
    pkt_num = stream_array[flow_id].pkt_num

    temp_g_resource = globalResource()
    temp_g_resource.global_resource_deepcopy(**g_resource.__dict__)

    total_slot_num_in_hyper_period = temp_g_resource.cur_total_sched_slot_num
    hop = 0
    for link_id in route:
        for j in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
            slot = (offset + j * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
            temp_g_resource.cqf_resource[link_id][slot].free_len -= pkt_num
            temp_g_resource.cqf_resource[link_id][slot].used_len += pkt_num
        hop += 1

    used_slot_num = 0
    total_pkt_num = 0
    for link_id in route:
        for j in range(total_slot_num_in_hyper_period):
            total_pkt_num += temp_g_resource.cqf_resource[link_id][j].used_len
            used_slot_num += 1

    density = 0
    average = total_pkt_num / used_slot_num
    for link_id in route:
        for j in range(total_slot_num_in_hyper_period):
            density += (temp_g_resource.cqf_resource[link_id][j].used_len - average) * \
                       (temp_g_resource.cqf_resource[link_id][j].used_len - average)
    density = density / used_slot_num

    return density


def _insert_flow_with_adjust_offset_density(sched: schedInfo,
                                            g_resource,
                                            stream_array: List[ITPStream]):
    sched.density = 0xFFFFFFFF
    sched.flag = FAIL

    flow_id = sched.flow_id
    period_in_slot = stream_array[flow_id].period_in_slot
    latency_req_in_slot = stream_array[flow_id].latency_req_in_slot

    route = stream_array[flow_id].route
    pkt_num = stream_array[flow_id].pkt_num

    total_slot_num_in_hyper_period = g_resource.cur_total_sched_slot_num
    for offset in range(period_in_slot):
        latency = offset + len(route) + 1
        if latency <= latency_req_in_slot:
            sched.flag = SUCCESS
            hop = 0
            for link_id in route:
                for j in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
                    slot = (offset + j * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                    if g_resource.cqf_resource[link_id][slot].free_len < pkt_num:
                        sched.flag = FAIL
                        break
                if sched.flag == FAIL:
                    break
                hop += 1
            # 找到最小的density
            if sched.flag == SUCCESS:
                new_density = _compute_flow_density_path_variance(sched, offset, g_resource, stream_array)
                if new_density <= sched.density:
                    sched.offset = offset
                    sched.density = new_density
        else:
            break

    if sched.density != 0xFFFFFFFF:
        sched.flag = SUCCESS
        hop = 0
        for link_id in route:
            for j in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
                slot = (sched.offset + j * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                g_resource.cqf_resource[link_id][slot].free_len -= pkt_num
                g_resource.cqf_resource[link_id][slot].used_len += pkt_num
            hop += 1
    else:
        sched.flag = FAIL


def _itp_generate_candidate_set_tradeoff(cur_solution,
                                         stream_array,
                                         rand_prob,
                                         candidate_set: List[tabuSchedSolution]
                                         ):
    """
    找到当前解的领域，产生候选解
    :param cur_solution: 当前的解
    :param stream_array:
    :param rand_prob:
    :return: candidate_set: 候选解的集合
    """
    # 控制从调度成功的流量集合中选取的流量的范围
    pro_num = 0
    # 从start处选择STEP_SIZE条流量
    start = 0

    if CANDIDATE_NUM * STEP_SIZE > cur_solution.cur_suc_num:
        sort_num = cur_solution.cur_suc_num
    else:
        sort_num = CANDIDATE_NUM * STEP_SIZE

    # 对cur_solution的sched_suc列表中的前sort_num条流进行排序
    for i in range(sort_num):
        for j in range(sort_num - i - 1):
            if itp_multi_stage_sort(cur_solution.sched_suc[j], cur_solution.sched_suc[j + 1], stream_array):
                temp = cur_solution.sched_suc[j]
                cur_solution.sched_suc[j] = cur_solution.sched_suc[j + 1]
                cur_solution.sched_suc[j + 1] = temp

    """逐个产生候选解"""
    # 1. 首先生成邻居
    # 2. 其次对邻居进行求解
    for num in range(CANDIDATE_NUM):
        candidate_set[num].solution_deepcopy(**cur_solution.__dict__)
        candidate_solution = candidate_set[num]

        # 清空候选解的tabuEntry
        candidate_solution.entry = tabuEntry()
        # 包括RAND_MAX
        # DEBUG
        # pick = randint(1, RAND_MAX) / RAND_MAX
        # rand_prob = 0

        pick = randint(0, RAND_MAX) / RAND_MAX

        """生成邻居"""
        # if-else分支
        if pick > rand_prob:

            for i in range(STEP_SIZE):
                # 从成功的流的start处开始选取，从后向前选择
                # 为什么要这么选？
                start = candidate_solution.cur_suc_num - (pro_num + 1) * STEP_SIZE + i
                if start < 0:
                    start = candidate_solution.cur_suc_num - STEP_SIZE + i

                # 选取start处的流
                flow_id = candidate_solution.sched_suc[start].flow_id

                candidate_solution.entry.out[i] = flow_id
                candidate_solution.sched_suc[start].flag = FAIL
                candidate_solution.sched_fail[cur_solution.cur_fail_num + i] = schedInfo()
                candidate_solution.sched_fail[cur_solution.cur_fail_num + i].sched_info_deepcopy(
                    **candidate_solution.sched_suc[start].__dict__
                )
                # 释放这条流所占用的队列资源
                route = stream_array[flow_id].route
                period_in_slot = stream_array[flow_id].period_in_slot
                pkt_num = stream_array[flow_id].pkt_num
                total_slot_num_in_hyper_period = candidate_solution.g_resource.cur_total_sched_slot_num
                hop = 0
                for link_id in route:
                    for k in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
                        slot = (candidate_solution.sched_suc[start].offset +
                                k * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                        candidate_solution.g_resource.cqf_resource[link_id][slot].used_len -= pkt_num
                        candidate_solution.g_resource.cqf_resource[link_id][slot].free_len += pkt_num
                    hop += 1

            # 从start开始，调度成功的流集合中STEP_SIZE个空缺的位置需要补齐
            for i in range(start + 1, candidate_solution.cur_suc_num):
                candidate_solution.sched_suc[i - STEP_SIZE] = schedInfo()
                candidate_solution.sched_suc[i - STEP_SIZE].sched_info_deepcopy(
                    **candidate_solution.sched_suc[i].__dict__
                )
            pro_num += 1

        else:
            # 调度成功的流，依次从后往前随机地与任意位置的流交换
            for i in range(candidate_solution.cur_suc_num):
                # randint(a,b)，a<=x<=b
                exchange = randint(0, candidate_solution.cur_suc_num - 1)
                # 这儿相当于是交换指针，不需要深拷贝
                temp = candidate_solution.sched_suc[candidate_solution.cur_suc_num - 1 - i]
                candidate_solution.sched_suc[candidate_solution.cur_suc_num - 1 - i] = \
                    candidate_solution.sched_suc[exchange]
                candidate_solution.sched_suc[exchange] = temp
                if candidate_solution.cur_suc_num - 1 - i == 0:
                    break

            # 从后向前从调度成功的流中选取五条流，加入到调度失败的流的集合中
            for i in range(STEP_SIZE):
                start = candidate_solution.cur_suc_num - STEP_SIZE + i
                if start < 0:
                    print('The step size exceed the flow success set size')

                candidate_solution.entry.out[i] = candidate_solution.sched_suc[start].flow_id
                candidate_solution.sched_suc[start].flag = FAIL
                candidate_solution.sched_fail[candidate_solution.cur_fail_num + i] = schedInfo()
                candidate_solution.sched_fail[candidate_solution.cur_fail_num + i].sched_info_deepcopy(
                    **candidate_solution.sched_suc[start].__dict__
                )

                flow_id = candidate_solution.sched_suc[start].flow_id

                route = stream_array[flow_id].route
                period_in_slot = stream_array[flow_id].period_in_slot
                pkt_num = stream_array[flow_id].pkt_num
                total_slot_num_in_hyper_period = candidate_solution.g_resource.cur_total_sched_slot_num
                hop = 0
                for link_id in route:
                    for k in range(math.ceil(total_slot_num_in_hyper_period / period_in_slot)):
                        slot = (candidate_solution.sched_suc[start].offset +
                                k * period_in_slot + hop + 1) % total_slot_num_in_hyper_period
                        candidate_solution.g_resource.cqf_resource[link_id][slot].used_len -= pkt_num
                        candidate_solution.g_resource.cqf_resource[link_id][slot].free_len += pkt_num
                    hop += 1

        # 更新调度成功和调度失败的流的数目
        candidate_solution.cur_suc_num -= STEP_SIZE
        candidate_solution.cur_fail_num += STEP_SIZE

        """对邻居进行求解"""
        if pick > rand_prob:
            # 找到最有可能被调度成功的STEP_SIZE条流
            for i in range(STEP_SIZE):
                # range的范围为[begin, end)
                for j in range(candidate_solution.cur_fail_num - 2, i - 1, -1):
                    if itp_multi_stage_sort(candidate_solution.sched_fail[j],
                                            candidate_solution.sched_fail[j + 1],
                                            stream_array):
                        temp = candidate_solution.sched_fail[j]
                        candidate_solution.sched_fail[j] = candidate_solution.sched_fail[j + 1]
                        candidate_solution.sched_fail[j + 1] = temp

            # 尝试将未调度成功的流插入到调度成功的流的集合中
            for i in range(candidate_solution.cur_fail_num):
                _insert_flow_with_adjust_offset_density(candidate_solution.sched_fail[i],
                                                        candidate_solution.g_resource,
                                                        stream_array
                                                        )
                if candidate_solution.sched_fail[i].flag == SUCCESS:
                    candidate_solution.sched_suc[candidate_solution.cur_suc_num] = schedInfo()
                    candidate_solution.sched_suc[candidate_solution.cur_suc_num].sched_info_deepcopy(
                        **candidate_solution.sched_fail[i].__dict__
                    )
                    candidate_solution.cur_suc_num += 1
                    candidate_solution.entry.inn[candidate_solution.entry.in_num] = \
                        candidate_solution.sched_fail[i].flow_id
                    candidate_solution.entry.in_num += 1
        else:
            # 交换未调度成功的任意两条流，打乱顺序
            for i in range(candidate_solution.cur_fail_num):
                switch1 = randint(0, candidate_solution.cur_fail_num - 1)
                switch2 = randint(0, candidate_solution.cur_fail_num - 1)
                temp = candidate_solution.sched_fail[switch1]
                candidate_solution.sched_fail[switch1] = candidate_solution.sched_fail[switch2]
                candidate_solution.sched_fail[switch2] = temp

            # 依次将未调度成功的流插入到调度成功的流的集合中
            for i in range(candidate_solution.cur_fail_num):
                _insert_flow_with_adjust_offset_random(candidate_solution.sched_fail[i],
                                                       candidate_solution.g_resource,
                                                       stream_array)
                if candidate_solution.sched_fail[i].flag == SUCCESS:
                    candidate_solution.sched_suc[candidate_solution.cur_suc_num] = schedInfo()
                    candidate_solution.sched_suc[candidate_solution.cur_suc_num].sched_info_deepcopy(
                        **candidate_solution.sched_fail[i].__dict__
                    )
                    candidate_solution.cur_suc_num += 1
                    candidate_solution.entry.inn[candidate_solution.entry.in_num] = \
                        candidate_solution.sched_fail[i].flow_id
                    candidate_solution.entry.in_num += 1

        i = 0
        j = 0
        # 更新调度失败的流的集合
        temp_num = candidate_solution.cur_fail_num
        while i < candidate_solution.cur_fail_num:
            if candidate_solution.sched_fail[i].flag == SUCCESS:
                i += 1
                temp_num -= 1
            else:
                if j < i:
                    candidate_solution.sched_fail[j] = candidate_solution.sched_fail[i]
                j += 1
                i += 1

        candidate_solution.cur_fail_num = temp_num

        # 写回
        candidate_set[num] = candidate_solution


def _compare_tabu_entry(entry1, entry2):
    for i in range(STEP_SIZE):
        flag = TABU_ENTRY_UNEQUAL
        for j in range(STEP_SIZE):
            if entry1.out[i] == entry2.out[j]:
                flag = TABU_ENTRY_EQUAL
                break
        if flag == TABU_ENTRY_UNEQUAL:
            return TABU_ENTRY_UNEQUAL

    return TABU_ENTRY_EQUAL


def itp_tabu_sched_out_tradeoff(link_array,
                                stream_array,
                                instance_array,
                                slot,
                                tsn_sched_set: schedSet,
                                g_resource,
                                rand_prob
                                ):
    # 初始解
    init_solution: tabuSchedSolution = tabuSchedSolution()
    # 历史最优解
    best_so_far: tabuSchedSolution = tabuSchedSolution()
    # 当前的解，从当前的解出发找邻域
    cur_solution: tabuSchedSolution = tabuSchedSolution()
    # 候选集中的最优解
    # cur_best_solution: tabuSchedSolution = tabuSchedSolution()
    # 候选解集合
    candidate_set: List[tabuSchedSolution] = [tabuSchedSolution() for i in range(CANDIDATE_NUM)]

    # 历史最优解重复出现的次数
    repeat_num = 0

    # 禁忌列表
    tabu_tbl = tabuTable()
    # 禁忌列表的命中次数
    hit_num = 0

    # 1. 生成初始解
    # while init_solution.cur_suc_num <= STEP_SIZE + 1:
    _itp_generate_init_solution_random(stream_array,
                                       tsn_sched_set,
                                       g_resource,
                                       init_solution)
    best_so_far.solution_deepcopy(**init_solution.__dict__)
    cur_solution.solution_deepcopy(**init_solution.__dict__)

    loop_num = 0

    # 2. 循环
    # for loop_num in range(MAX_LOOP_NUM):
    while loop_num < MAX_LOOP_NUM:
        if best_so_far.cur_suc_num == tsn_sched_set.cur_flow_num:
            print('have found optimal')
            print('best_so_far.cur_suc_num: %d' % best_so_far.cur_suc_num)
            cur_sum = 0
            for sf in best_so_far.sched_suc:
                if sf.flag == FAIL:
                    print('error - failed flow: %d' % sf.flow_id)
                    cur_sum += 1
            print("total failed flow in best so far solution: %d" % cur_sum)
            break

        # 2-a. 生成候选解的集合
        _itp_generate_candidate_set_tradeoff(cur_solution,
                                             stream_array,
                                             rand_prob,
                                             candidate_set)

        # 2-b. 找到候选解中的最优解
        # 初始化候选解中的最优解
        cur_best_solution = tabuSchedSolution()
        cur_best_solution.init_sched_solution(len(stream_array))
        # 找到所有候选解中最佳的解
        best_candidate = 0
        for i in range(CANDIDATE_NUM):
            if candidate_set[i].cur_suc_num >= cur_best_solution.cur_suc_num:
                best_candidate = i
        cur_best_solution.solution_deepcopy(**candidate_set[best_candidate].__dict__)

        # 2-c. 对禁忌列表的操作
        # 如果候选解中最佳的解好过历史最好的解
        if cur_best_solution.cur_suc_num >= best_so_far.cur_suc_num:
            if cur_best_solution.cur_suc_num == best_so_far.cur_suc_num:
                print("repeat_num: %d" % repeat_num)
                repeat_num += 1
                if repeat_num >= MAX_REPEAT_NUM:
                    print("repeat flag: %d" % repeat_num)
                    break
            else:
                repeat_num = 0

            for i in range(tabu_tbl.cur_num):
                if _compare_tabu_entry(cur_best_solution.entry, tabu_tbl.entry[i]) == TABU_ENTRY_EQUAL:
                    print('hit')
                    hit_num += 1

            # 将候选解中的最优解设为历史最优解
            best_so_far = tabuSchedSolution()
            best_so_far.solution_deepcopy(**cur_best_solution.__dict__)
            cur_solution = tabuSchedSolution()
            cur_solution.solution_deepcopy(**cur_best_solution.__dict__)
            # 将当前最优解的entry加入到禁忌列表的最前端
            tabu_tbl.entry[0] = tabuEntry()
            tabu_tbl.entry[0].tabu_entry_deepcopy(**cur_best_solution.entry.__dict__)
            if tabu_tbl.cur_num == 0:
                tabu_tbl.cur_num += 1

            temp_tabu_tbl_num = tabu_tbl.cur_num
            j = 0
            # TODO:
            # 这里有个可能的bug
            # 1. 实际上的循环次数并不是tabu_tbl.cur_num
            for i in range(1, tabu_tbl.cur_num):
                if _compare_tabu_entry(cur_solution.entry, tabu_tbl.entry[i]) == TABU_ENTRY_EQUAL:
                    i += 1
                    temp_tabu_tbl_num -= 1
                else:
                    if j < i:
                        tabu_tbl.entry[j] = tabu_tbl.entry[i]
                    i += 1
                    j += 1
            tabu_tbl.cur_num = temp_tabu_tbl_num
        else:
            repeat_num = 0
            cur_best_solution = tabuSchedSolution()
            cur_best_solution.init_sched_solution(len(stream_array))
            cur_best = 0
            for i in range(CANDIDATE_NUM):
                compare_flag = TABU_ENTRY_UNEQUAL
                for j in range(tabu_tbl.cur_num):
                    if _compare_tabu_entry(candidate_set[i].entry, tabu_tbl.entry[j]) == TABU_ENTRY_EQUAL:
                        compare_flag = TABU_ENTRY_EQUAL
                        break

                # TODO：
                if compare_flag == TABU_ENTRY_EQUAL:
                    print('hit')
                    hit_num += 1
                    # 多余的continue
                    continue
                else:
                    if candidate_set[i].cur_suc_num >= cur_best_solution.cur_suc_num:
                        cur_best = i
            cur_best_solution.solution_deepcopy(**candidate_set[cur_best].__dict__)

            if cur_best_solution.cur_suc_num > 0:
                cur_solution = tabuSchedSolution()
                cur_solution.solution_deepcopy(**cur_best_solution.__dict__)

            # TODO:
            # 为什么此时要将当前最优解的表项加到禁忌列表的最后呢？
            if tabu_tbl.cur_num >= TABU_TBL_SIZE:
                for i in range(tabu_tbl.cur_num - 1):
                    tabu_tbl.entry[i] = tabu_tbl.entry[i + 1]
                i = tabu_tbl.cur_num - 1
                tabu_tbl.entry[i].tabu_entry_deepcopy(**cur_best_solution.entry.__dict__)
            else:
                tabu_tbl.entry[tabu_tbl.cur_num].tabu_entry_deepcopy(**cur_best_solution.entry.__dict__)
                tabu_tbl.cur_num += 1

        print("best so far suc num: %d" % best_so_far.cur_suc_num)

        loop_num += 1

    # 3. 输出解
    g_resource = best_so_far.g_resource

    for i in range(tsn_sched_set.cur_flow_num):
        tsn_sched_set.sched[i].flag = FAIL

    for i in range(best_so_far.cur_suc_num):
        for j in range(tsn_sched_set.cur_flow_num):
            if best_so_far.sched_suc[i].flow_id == tsn_sched_set.sched[j].flow_id:
                tsn_sched_set.sched[j] = best_so_far.sched_suc[i]
                break

    tsn_sched_set.cur_suc_num = best_so_far.cur_suc_num
    sum_cur = 0
    for sched in tsn_sched_set.sched:
        if sched.flag == FAIL:
            print("flow_id: %d" % sched.flow_id)
            sum_cur += 1
    print("failed flow in tsn_sched_set: %d" % sum_cur)

    return loop_num
